package ljl.codetop300;

import commons.TreeNode;

import java.util.LinkedList;

public class _111_min_deep {

  static class test {
    public int minDepth(TreeNode root) {
      if (root == null) return 0;
      if (root.left == null && root.right == null) return 1;
      int left = minDepth(root.left);
      if (root.right == null) return left + 1;
      int right = minDepth(root.right);
      if (root.left == null) return right + 1;
      return 1 + Math.min(left, right);
    }
  }

  static class off2 {
    public int minDepth(TreeNode root) {
      if (root == null) return 0;
      record Node(int d, TreeNode node) {
      }
      LinkedList<Node> q = new LinkedList<>();
      q.offer(new Node(1, root));
      while (!q.isEmpty()) {
        Node node = q.poll();
        TreeNode treeNode = node.node;
        if (treeNode.left == null && treeNode.right == null) return node.d;
        if (treeNode.left != null) q.offer(new Node(node.d + 1, treeNode.left));
        if (treeNode.right != null) q.offer(new Node(node.d + 1, treeNode.right));
      }
      return 0;
    }
  }
}
